package solution;

import java.util.*;

class Solution {
    public int[][] merge(int[][] arr) {
        int len = arr.length;

        if (len == 1) {
            return arr;
        }

        //将 intervals 按第一个元素从大到小排列
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return Integer.compare(a[0], b[0]);
            }
        });

        int i = 0, j = i + 1;
        int right = arr[i][1];
        int rightMax = arr[i][1];
        List<int[]> list = new ArrayList<>();
        while (i < len && j <= len) {
            if (j < len && rightMax >= arr[j][0]) {
                right = arr[j][1];
                rightMax = Math.max(right, rightMax);
            } else {
                int[] arr1 = new int[]{arr[i][0], rightMax};
                list.add(arr1);
                i = j;
                if (i >= len) {
                    break;
                } else {
                    right = arr[i][1];
                    rightMax = right;
                }
            }
            j++;
        }

        return list.toArray(new int[0][0]);
    }
}